/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */

#ifndef _CUBEFS_CORE_BITVECTOR_HPP
#define _CUBEFS_CORE_BITVECTOR_HPP

#include <cubefs/core/tools/btree.hpp>
#include <cubefs/core/tools/bitmap_page.hpp>
#include <iostream>

namespace cubefs {
namespace core {
namespace bitvector_ns {

inline static void here(int n = 0)
{
    std::cout<<"HERE: "<<n<<std::endl;
}

#pragma pack(1)

template <typename PageMgr, typename SmallType = short, typename LargeType = csize_t>
class node_page_base: public tree_page<PageMgr>
{
    LargeType _page_count;
    SmallType _index_in_parent;
    SmallType _level;
    SmallType _inserted;
    bool      _hasnt_label;

    typedef tree_page<PageMgr> base;

public:

    node_page_base(): base(), _page_count(0), _index_in_parent(0), _level(0), _inserted(-1)
    {
    }

    bool &hasnt_label() const
    {
        return (bool&)_hasnt_label;
    }

    SmallType &inserted_idx() const
    {
        return (SmallType&)_inserted;
    }

    LargeType &page_count() const
    {
        return (LargeType&)_page_count;
    }

    SmallType &index_in_parent() const
    {
        return (SmallType&)_index_in_parent;
    }

    SmallType &level() const
    {
        return (SmallType&)_level;
    }

    bool is_small() const
    {
        return base::get_key_size() == KEY_SIZE__SMALL;
    }

    bool is_medium() const
    {
        return base::get_key_size() == KEY_SIZE__MEDIUM;
    }

    bool is_large()
    {
        return base::get_key_size() == KEY_SIZE__LARGE;
    }

    bool is_huge()
    {
        return base::get_key_size() == KEY_SIZE__HUGE;
    }
};

class bitvector_metadata
{

    int     _cardinality;
    bool    _use_local_parenthesis;

public:
    bitvector_metadata() {}

    int &cardinality() const
    {
        return (int&)_cardinality;
    }

    bool &use_local_parenthesis() const
    {
        return (bool&)_use_local_parenthesis;
    }
};


template <typename PageMgr, typename Key = csize_t, typename IndexKey = csize_t, typename Metadata = bitvector_metadata,typename LevelType = short, long Indexes = 3, typename CountType = csize_t>
class root_node_page: public node_page_base<PageMgr, LevelType, CountType>
{

    typedef node_page_base<PageMgr, LevelType, CountType> base;
    typedef root_node_page<PageMgr, Key, IndexKey, Metadata, LevelType, Indexes, CountType> me;

    struct MapConstants: public GlobalConstants
    {
        static const int BLOCK_SIZE = PageMgr::PAGE_SIZE - sizeof(base) - sizeof (Metadata) - sizeof(typename PageMgr::page_t::ID);
    };

public:
    typedef packed_index_map<Key, typename PageMgr::page_t::ID, MapConstants, Indexes, IndexKey> map_t;

private:

    Metadata _metadata;

    typename PageMgr::page_t::ID _head_id;

    map_t _map;

public:

    static const long INDEXES = Indexes;

    typedef Key key_t;
    typedef typename PageMgr::page_t::ID value_t;

    root_node_page(): base(), _metadata(), _map()
    {
        base::set_root(true);
        base::set_bitmap(false);
    }

    map_t &map() const
    {
        return (map_t&)_map;
    }

    Metadata &metadata() const
    {
        return (Metadata&) _metadata;
    }

    typename PageMgr::page_t::ID &head_id()
    {
        return (typename PageMgr::page_t::ID&) _head_id;
    }

    void reindex()
    {
        map().reindex();
    }
};

template <typename PageMgr, typename Key = csize_t, typename IndexKey = csize_t, typename LevelType = short, long Indexes = 3, typename CountType = csize_t>
class node_page: public node_page_base<PageMgr, LevelType, CountType>
{

    typedef node_page_base<PageMgr, LevelType, CountType> base;
    typedef node_page<PageMgr, Key, IndexKey, LevelType, Indexes, CountType> me;

    struct MapConstants: public GlobalConstants
    {
        static const int BLOCK_SIZE = PageMgr::PAGE_SIZE - sizeof(base);
    };

public:
    typedef packed_index_map<Key, typename PageMgr::page_t::ID, MapConstants, Indexes, IndexKey> map_t;

private:

    map_t _map;

public:

    static const long INDEXES = Indexes;

    typedef Key key_t;
    typedef typename PageMgr::page_t::ID value_t;

    node_page(): base(), _map()
    {
        base::set_root(false);
        base::set_bitmap(false);
    }

    map_t &map() const
    {
        return (map_t&)_map;
    }

    void reindex()
    {
        map().reindex();
    }
};


#pragma pack()

#define BV_COMMA ,

#define BV_NODE_CAST_EXP(page, expression)              \
switch (page->is_root()*4 + page->get_key_size()) {     \
    case KEY_SIZE__SMALL : {                            \
        static_cast<small_node*>(page)->expression;     \
        break;                                          \
    }                                                   \
    case 4 + KEY_SIZE__SMALL : {                        \
        static_cast<root_small_node*>(page)->expression;\
        break;                                          \
    }                                                   \
    case KEY_SIZE__MEDIUM : {                           \
        static_cast<medium_node*>(page)->expression;    \
        break;                                          \
    }                                                   \
    case 4 + KEY_SIZE__MEDIUM : {                       \
        static_cast<root_medium_node*>(page)->expression;\
        break;                                          \
    }                                                   \
    case KEY_SIZE__LARGE : {                            \
        static_cast<large_node*>(page)->expression;     \
        break;                                          \
    }                                                   \
    case 4 + KEY_SIZE__LARGE : {                        \
        static_cast<root_large_node*>(page)->expression;\
        break;                                          \
    }                                                   \
    case KEY_SIZE__HUGE : {                             \
        static_cast<huge_node*>(page)->expression;      \
        break;                                          \
    }                                                   \
    default : {                                         \
        static_cast<root_huge_node*>(page)->expression; \
        break;                                          \
    }                                                   \
}

#define BV_NODE_CAST2(page, block)                                          \
switch (page->is_root() * 4 + page->get_key_size()) {                       \
    case KEY_SIZE__SMALL : {                                                \
        typedef small_node node_t;                                          \
        typedef root_small_node root_node_t;                                \
        node_t* __##page = static_cast<node_t*>(page);                      \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case 4 + KEY_SIZE__SMALL : {                                            \
        typedef small_node node_t;                                          \
        typedef root_small_node root_node_t;                                \
        root_node_t* __##page = static_cast<root_node_t*>(page);            \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__MEDIUM : {                                               \
        typedef medium_node node_t;                                         \
        typedef root_medium_node root_node_t;                               \
        node_t* __##page = static_cast<node_t*>(page);                      \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case 4 + KEY_SIZE__MEDIUM : {                                           \
        typedef medium_node node_t;                                         \
        typedef root_medium_node root_node_t;                               \
        root_node_t* __##page = static_cast<root_node_t*>(page);            \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__LARGE : {                                                \
        typedef large_node node_t;                                          \
        typedef root_large_node root_node_t;                                \
        node_t* __##page = static_cast<node_t*>(page);                      \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case 4 + KEY_SIZE__LARGE : {                                            \
        typedef large_node node_t;                                          \
        typedef root_large_node root_node_t;                                \
        root_node_t* __##page = static_cast<root_node_t*>(page);            \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__HUGE : {                                                 \
        typedef huge_node node_t;                                           \
        typedef root_huge_node root_node_t;                                 \
        node_t* __##page = static_cast<node_t*>(page);                      \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    default : {                                                             \
        typedef huge_node node_t;                                           \
        typedef root_huge_node root_node_t;                                 \
        root_node_t* __##page = static_cast<root_node_t*>(page);            \
        block;                                                              \
    }                                                                       \
}


#define BV_NODE_CAST3(page, page2, block)                                   \
switch (page->is_root() * 4 + page->get_key_size()) {                       \
    case KEY_SIZE__SMALL : {                                                \
        small_node* __##page = static_cast<small_node*>(page);              \
        small_node* __##page2 = static_cast<small_node*>(page2);            \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case 4 + KEY_SIZE__SMALL : {                                            \
        root_small_node* __##page = static_cast<root_small_node*>(page);    \
        root_small_node* __##page2 = static_cast<root_small_node*>(page2);  \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__MEDIUM : {                                               \
        medium_node* __##page = static_cast<medium_node*>(page);            \
        medium_node* __##page2 = static_cast<medium_node*>(page2);          \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case 4 + KEY_SIZE__MEDIUM : {                                           \
        root_medium_node* __##page = static_cast<root_medium_node*>(page);  \
        root_medium_node* __##page2 = static_cast<root_medium_node*>(page2);\
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__LARGE : {                                                \
        large_node* __##page = static_cast<large_node*>(page);              \
        large_node* __##page2 = static_cast<large_node*>(page2);            \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case 4 + KEY_SIZE__LARGE : {                                            \
        root_large_node* __##page = static_cast<root_large_node*>(page);    \
        root_large_node* __##page2 = static_cast<root_large_node*>(page2);  \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__HUGE : {                                                 \
        huge_node* __##page = static_cast<huge_node*>(page);                \
        huge_node* __##page2 = static_cast<huge_node*>(page2);              \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    default : {                                                             \
        root_huge_node* __##page = static_cast<root_huge_node*>(page);      \
        root_huge_node* __##page2 = static_cast<root_huge_node*>(page2);    \
        block;                                                              \
    }                                                                       \
}


#define BV_ROOT_CAST2(page, block)                                          \
switch (page->get_key_size()) {                                             \
    case KEY_SIZE__SMALL : {                                                \
        root_small_node* __##page = static_cast<root_small_node*>(page);    \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__MEDIUM : {                                               \
        root_medium_node* __##page = static_cast<root_medium_node*>(page);  \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__LARGE : {                                                \
        root_large_node* __##page = static_cast<root_large_node*>(page);    \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    case KEY_SIZE__HUGE : {                                                 \
        root_huge_node* __##page = static_cast<root_huge_node*>(page);      \
        block;                                                              \
        break;                                                              \
    }                                                                       \
    default : {                                                             \
        root_huge_node* __##page = static_cast<root_huge_node*>(page);      \
        block;                                                              \
    }                                                                       \
}

template <typename PageMgr, typename SmallType = short>
class bitvector
{
    typedef typename PageMgr::page_t        page_t;
    typedef typename PageMgr::page_t::ID    ID;
    typedef typename PageMgr::txn_t         txn_t;

    ID _root;
    ID _marked_page_id;
    index_t _marked_bit_idx;

    PageMgr &_mgr;
    csize_t _size;
    int _node_size;

    int _max_node_capacity;

public:

    template <typename IdxType = int>
    class iterator;

    static const int LABEL             = 0;
    static const int BIT_FOR_PARENT    = 1;
    static const int PATH              = 2;

    typedef tree_page<PageMgr>                           tree_node;

    typedef node_page_base<PageMgr>                      node_base;

    typedef node_page<PageMgr, csize_t, csize_t>         huge_node;
    typedef node_page<PageMgr, int, csize_t>             large_node;
    typedef node_page<PageMgr, int, int>                 medium_node;
    typedef node_page<PageMgr, short, int>               small_node;

    typedef root_node_page<PageMgr, csize_t, csize_t>    root_huge_node;
    typedef root_node_page<PageMgr, int, csize_t>        root_large_node;
    typedef root_node_page<PageMgr, int, int>            root_medium_node;
    typedef root_node_page<PageMgr, short, int>          root_small_node;

    typedef bitmap_page<PageMgr>                         bitmap_node;
    typedef bitvector<PageMgr, SmallType>                me;

    typedef iterator<>                                   iterator_t;

    bitvector(PageMgr &mgr):
            _root(),
            _mgr(mgr)
    {
        _max_node_capacity = -1;
        _marked_page_id = 0;
        _root.clear();
    }

    bitvector(PageMgr &mgr, const ID &root): _root(root), _mgr(mgr)
    {
        _max_node_capacity = -1;
        _marked_page_id = 0;
    }

    ID &root() const
    {
        return (ID&) _root;
    }

    PageMgr &mgr()
    {
        return _mgr;
    }

    csize_t get_size() const
    {
        return _size;
    }

    int& max_node_capacity()
    {
        return _max_node_capacity;
    }

    index_t &marked_bit_idx()
    {
        return (index_t &)_marked_bit_idx;
    }

    ID &marked_page_id()
    {
        return (ID&) _marked_page_id();
    }

    index_t get_node_bits()
    {
        return 4;
    }

    index_t get_data_bits()
    {
        return 0;
    }

#include "bitvector/insert.hpp"
#include "bitvector/remove.hpp"
#include "bitvector/tools.hpp"
#include "bitvector/iterator.hpp"

};

} //bitvector
} //core
} //cubefs

#endif // _CUBEFS_BITVECTOR_HPP
